#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        int left = 0, right = arr.size() - 1;
        srand(time(nullptr));
        qsort(arr, left, right);
        vector<int>v;
        for (int i = 0; i < k; i++)
        {
            v.push_back(arr[i]);
        }
        return v;
    }
    void qsort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;
        int pivot = rand() % (right - left + 1) + left;
        swap(nums[left], nums[pivot]);
        pivot = left;
        int key = nums[pivot];
        int begin = left, end = right;
        while (begin < end)
        {
            while (begin < end && nums[end] >= key)
            {
                end--;
            }
            nums[pivot] = nums[end];
            pivot = end;
            while (begin < end && nums[begin] <= key)
            {
                begin++;
            }
            nums[pivot] = nums[begin];
            pivot = begin;
        }
        nums[pivot] = key;
        qsort(nums, left, pivot - 1);
        qsort(nums, pivot + 1, right);

    }
};